Date: Wed, 20 Nov 1996 21:47:09 GMT
Server: NCSA/1.5
Content-type: text/html

<TITLE>Computer Science 410 --- Spring 1996</TITLE>
<!--- This is a comment --->
<!BODY background="http://home.netscape.com/home/bg/paper/greenwhite_paper.gif">
<!BODY background="http://home.netscape.com/home/bg/paper/orange_paper.gif">
<!BODY background="http://home.netscape.com/home/bg/stucco/yellow_stucco.gif">
<!BODY background="http://home.netscape.com/home/bg/paper/yellow_paper.gif">
<!BODY background="http://home.netscape.com/home/bg/paper/teal_paper.gif">
<!BODY background="http://home.netscape.com/home/bg/rock/yellow_rock.gif">
<!BODY background="http://home.netscape.com/home/bg/weave/lipurple_weave.gif">
<!BODY background="http://home.netscape.com/home/bg/weave/yellow_weave.gif">
<!BODY background="http://home.netscape.com/home/bg/fabric/pink_fabric.gif">
<!BODY bgcolor= #AFEEEE> <! pale turqouise>
<!BODY bgcolor= #FFDAB9> <! peach puff>
<BODY bgcolor= #F0808> <! light coral>


<H2>Computer Science 535 - Fall 1996</h2>
<!WA0><a href="http://cs-www.bu.edu/Home.html">
Computer Science Department, Boston University</a>
</hr>


 <h3>Current information</h3>
 <strong>Homework:</strong> (and its solution, after the submission
date), in the directory ~cs535/gacs/handout.
 <hr>
 <h3>Useful pointers</h3>
 <hr>

 <strong>Instructor:</strong>Peter Gacs,
 <strong>Email:</strong> gacs@cs.bu.edu,
 <strong>Phone:</strong> 353-2015,
 <strong>Office:</strong> MCS 277
 <br>
 <strong>Office hours:</strong> Tue 3:30-5:00, Wed 1:30-3:00

 <p>
 <strong>Time:</strong> Tue, Thu 2:00-3:30, 
 <strong>Place:</strong> MCS B29

 <h3>Texts</h3>
  Required:
 <ul>
  <li> Lovasz: Computation Complexity (translation by Gacs).
  file gacs/comp-th-notes.ps on  ftp.cs.bu.edu (about 180 pages).
  Print on publp, (two-sided), bind at the BU Copy Center.
 </ul>
  Recommended:
 <ul>  
  <li> <!WA1><a href="http://cs-www.bu.edu/faculty/lnd/ftp/toc/">
Leonid A. Levin: Fundamentals of Computing</a>

  <li> Lewis-Papadimitriou: Elements of the Theory of Computation,
Prentice-Hall 1981
  <li> Hopcroft-Ullmann: Introduction to Automata Theory, Languages and
Computation Addison-Wesley 1979.
  <li> Papadimitriou: Computational Complexity, AW 1994, ISBN 0-201-53082-1
  </ul>
<hr>

 <h3>Description</h3>
  Topics covered:
  Machine models.  Undecidability.  Complexity notions.  Some
important algorithms.  Compression and speed-up theorems.
Nondeterminism.  NP problems.  Randomized algorithms.  Prime number
tests.  Description complexity, randomness, information.
Pseudorandom generators.  Quadratic residuosity, and public-key
cryptography.  Parallel algorithms.  Exponential lower bounds,
alternating machines and games.  Decision trees.  Communication
complexity.
 
<hr>

 <h3>Homework</h3>
  Homework:
  Given every Tuesday.  Must be returned next Tuesday.  50% credit if
late by one class period, no credit thereafter.
  Each student can get at most one exception for not submitting homework on
time.

 <h3>Exams</h3>
  One midterm (one class period length) and one final exam.
  Only a single double-sided sheet of handwritten notes
("crib-sheet") is allowed.
  The final exam covers the whole material.

 <h3>Grading</h3>
  In the final grade, your homeworks count 30% and your exams 30% and 40%.
  An Incomplete grade will only be given in exceptional circumstances.

 <h3>Cooperation</h3>
  It is OK to discuss the homework with your classmates, but you must write
it up yourself and understand it.
  I will ask questions if the solution is suspicious.
 <hr>
</body>
